1. Field of the Invention
The present invention relates to a layered decoding architecture which reduces the hardware area and improves hardware utilization while retaining the converge speed, and thus can be applied to the decoding of low-density parity check (LDPC) codes with fewer buffers.
2. Description of Related Art
The concept of the decoding of (LDPC) codes can be referred to in FIG. 2 and FIG. 3. FIG. 3 is a Tanner graph expressing the connection of check nodes to variable nodes in the parity-check matrix shown in FIG. 2. As shown, one row of the parity-check matrix corresponds to a check node and a column corresponds to a variable node. In the parity-check matrix, if the i-th row and the j-th column behave 1, then the check node i and the variable node j in the Tanner graph will be connected by an edge (line). Otherwise, there is no connection between them.
From FIG. 4., variable node j calculates a variable-to-check message Q, using the extrinsic information Ri′j obtained from the neighboring check nodes i′, except for the check node i, and by using a channel value. This extrinsic information is a message that excludes the information that the receiving check node i already knows. For check node i, the variable-to-check message Qij from variable node j to check node i will exclude the check-to-variable message Rij from check node i to variable node j. In FIG. 5., check node i uses the variable-to-check information obtained from the neighboring variable node, except for variable node j, to obtain a check-to-variable message Rij, which is then sent to variable node j. This extrinsic information is also a message that excludes the information already known by the receiving variable node j. For variable node j, the check-to-variable message Rij from check node i to variable node j will exclude the variable-to-check message Qij from variable node j to check node i, and other messages obtained will be calculated.
Generally, a decoding process has three phases: variable node processing, check node processing and A Posteriori Probability (APP) processing. The conventional layered decoding architecture is described as follows. Let N (i) be the set of all the variable nodes connected to check node i. Equation (1) is used in the variable node processing phase to obtain the variable-to-check message (Q) for all variable nodes j connected to the check nodes in the check-node layer being processed. Equation (2) is used in the check-node processing phase to obtain the check-to-variable message (R) of all check nodes i in the check-node layer being processed. Equation (3) is used to update the APP value of all the variable nodes j connected to the check node layer being processed after the processing of all check nodes in the check-node layer has been completed according to equation (2). The detailed equations used in the layered decoding algorithm are as follows:Qij=APPj−Rij, ∀jεN(i)  (1)Rij′=α└ΠkεN(i)/{j}sign(Qik)┘minkεN(i)/{j}{|Qik|}, ∀jεN(i)  (2)APPj′=Qij+Rij′, ∀jεN(i)  (3)
In equation (2), α is a normalization factor. A conventional layered decoding architecture executes the decoding by storing the APP values. When the check node begins a new operation, the check-to-variable message obtained in the previous decoding iteration will be deducted from the APP value to obtain the variable-to-check message. The variable-to-check message will be buffered, and also inserted into the check node equation to obtain the check-to-variable message, which is then registered in check-to-variable message shift registers and added to the variable-to-check message in the buffer in order to simultaneously obtain an updated APP value at the same time. The updated APP value will then be sent to the APP routing network.
From FIG. 6., when processing a layer, the APP routing network unit 32 retrieves the updated APP values from the APP memory 31 and then routes the updated APP values to ensure that the updated APP values are mapped to their corresponding check nodes. Then, the first calculation unit 33, it retrieves the total product of the variable-to-check message signs, a minimal variable-to-check message magnitude index, and the minimal and the second minimal variable-to-check message magnitudes for the current check-node layer obtained in the previous decoding iteration. The check-to-variable message sign can be obtained from the total product of the variable-to-check message signs and the variable-to-check message sign obtained from the variable-to-check message sign memory 35. The check-to-variable message magnitude can be obtained from the minimal variable-to-check message magnitude index, and the minimal and the second minimal variable-to-check message magnitudes so as to obtain the complete check-to-variable message. Subsequently, the first calculation unit deducts the check-to-variable message from the obtained APP value, as shown by Q=APP−R, to obtain the variable-to-check message. The variable-to-check message will be buffered in the variable-to-check message magnitude buffer 34 and the variable-to-check message sign memory (Q sign memory) 35 and forwarded to the check-node processor 36. The check-node processor 36 includes a comparator 361, a register 362, a normalizer 363, and a check-to-variable message shift register 364. The comparator 361 compares the obtained variable-to-check messages to determine the minimal and the second minimal variable-to-check node magnitudes, the total product of the variable-to-check message signs and the minimal variable-to-check message magnitude index. This minimal variable-to-check message magnitude index includes the location of the variable node corresponding to the minimal variable-to-check message magnitude on a check node. These obtained values are temporarily stored in the register 362. After the check node operation is completed, the final obtained values are sent to the normalizer 363, which normalizes the minimal and the second minimal values, and to the check-to-variable message shift register 364 and the second calculation unit 37. The second calculation unit updates the APP value, as shown by APP=Q+R, to obtain an updated APP value, which is then stored to the APP memory. An APP sign routing network 38 ensures that the APP signs of the updated APP values are routed to each corresponding variable node. Those routed APP signs are stored to the APP sign memory 39 to enable codeword output after decoding is complete.
However, it is necessary to retrieve the check-to-variable message obtained during this iteration in this operation in order to update the APP value. The time required for calculating the check node equation relates to the row weight of the current check-node layer. The higher the row weight, the more time that is required for the check node process. In the conventional architecture, the variable-to-check message (Q) obtained during this operation must be buffered. Before the check node equation in this operation is completed, it needs to buffer the variable-to-check message. Therefore, the size of the buffer is proportional to the row weight.
In the above, for the conventional architecture, the updating process of the APP value in each operation requires the inclusion of the check-to-variable message calculated during this operation. As shown in FIG. 6, in the case where the APP value from the previous operation has not yet been updated, the decoding action in the next operation will be delayed until the updating of the APP value is completed as the corresponding APP values, which are not yet updated. This type of action results in a number of decoding components becoming idle. In addition, until the comparison of the last variable-to-check message magnitude in this operation is finished, the components responsible for updating the APP value cannot work either. Therefore, the performance of the conventional architecture depends on the structure of the parity-check matrix, severely impacting the hardware utilization.
The conventional layered decoding architecture, which stores the APP value and updates the layered computation in turn, also has scheduling problems. Not only is the hardware utilization low, but more variable-to-check message magnitude buffers are also required, thereby increasing the hardware area. Therefore, the conventional architecture cannot meet the needs of users in actual use.